1. Technical Field
This relates to the design and manufacture of very large scale integrated (“VLSI”) circuits and, more particularly, to a maximal tile generation technique suitable for use in conjunction with the design and manufacture of VLSI circuits.
2. Description of the Relevant Art
A VLSI circuit is typically composed of a plurality of layers, each having a plurality of generally rectangular shaped components positioned thereon, oriented in either the horizontal or vertical axis. VLSI circuit designers commonly refer to these generally rectangular shaped components as “component tiles” and to the generally rectangular shaped open spaces that surround the component tiles as “space tiles.” Component tiles that are to be connected on a VLSI circuit are said to form a “net”, while any component tile not connected to a particular net is considered to be an obstruction to that net. Two tiles on the same layer are said to be “adjacent” if they touch along their edges and “overlapping” if there is even a single point located within the interior of both tiles. A set of tiles positioned within a routing area is said to be “maximal” if no two tiles are either overlapping or adjacent on their left or right edges.
One step in the design of a VLSI circuit is to select the wire paths that extend through the space tiles to connect the electrically equivalent component tiles that form nets. A current technique used to determine these paths utilizes a tile expansion algorithm. More specifically, clear space around the component tiles forming a net is fractured into maximal space tiles. Adjoining ones of these maximal space tiles are used to define the most efficient tile path between two components. The path of the actual connection between the components, known as the wire path, is then defined as the route through the space tile path from the component source tile to the component destination tile.
The aforementioned technique for selecting the wire paths for a VLSI circuit design suffers from two drawbacks, both of which may add to the cost of VLSI circuits manufactured in accordance with the design. First, if defined in accordance with the above-described manner, a tile path is not necessarily the optimal tile path through the clear space. Second, since the width of a tile path is typically much larger than the width of a wire path, multiple wire paths may exist through a given tile path. If the wire path located within the tile path is arbitrarily selected, the selected wire path is not necessarily the most efficient wire path potentially located within the tile path.